package com.example.question.tree.tree2;

import com.example.question.tree.tree1.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2023-07-12
 * @Author Jonathan
 */
public class Code08_257 {

    public static void main(String[] args) {
        System.out.println("->".length());
        String s = "123";
        String s1 = new String(s);
    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<List<Integer>> path = path(root);
        List<String> ret = new ArrayList<>();
        for (List<Integer> list : path) {
            StringBuilder builder = new StringBuilder();
            builder.append(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                builder.append("->").append(list.get(i));
            }
            ret.add(builder.toString());
        }
        return ret;
    }

    public List<List<Integer>> path(TreeNode node) {
        List<List<Integer>> ret = new ArrayList<>();
        dfs(node, ret, new ArrayList<>());
        return ret;
    }

    private void dfs(TreeNode node, List<List<Integer>> ret, List<Integer> path) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        if (node.left == null && node.right == null) {
//            path.add(node.val);
            //  不能指向同一个
            ret.add(new ArrayList<>(path));
        }
        dfs(node.left, ret, path);
        dfs(node.right, ret, path);
        // 回溯的过程中，将当前节点从path中删除
        path.remove(path.size() - 1);
    }


}
